package acwing_05;
import java.util.*;
import java.io.*;
public class _2_01背包问题_1朴素做法_carl版 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N = 1010;
	static int n;// 物品数量
	static int m;// 背包容积
	static int v[] = new int[N];// 第i件物品体积
	static int w[] = new int[N];// 第i件物品价值
	static int dp[][] = new int[N][N]; // dp[i][j]
	public static void main(String[] args) throws IOException {
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			v[i] = Integer.parseInt(st.nextToken());
			w[i] = Integer.parseInt(st.nextToken());
		}
		
		
		// 初始化首行（acwing视频的方式不需要初始化数组，但是很难理解，这里采用carl的思路先进行初始化
		// 之后的代码将递推完的数组输出，通过公式就很容易理解
		for(int i = 0; i <= m; i++) {
			// 如果容积i 大于等于 物品0的体积，则赋值为物品0的价值
			if(i >= v[0]) {
				dp[0][i] = w[0];
			}
		}
		
		// i是物品行 j是容积列
		for(int i = 1; i < n; i++) {
			for(int j = 1; j <= m ; j++) {
				// 如果当前物品体积比当前容积大，则不放本物品，放上面一个格子的总价值
				if(v[i] > j) {
					dp[i][j] = dp[i - 1][j];
				}else {
					// 公式，取不放本物品和放本物品的最大值
					// 不放本物品：dp[i - 1][j]
					// 放本物品：  dp[i - 1][j - v[i]] + w[i]
					dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
				}
			}
		}
		int res = 0;
		// 拿到最后一列(最大容积列)中所有物品的最大价值
		for(int i = 0; i <= n; i++) {
			res = Math.max(res, dp[i][m]);// i行m列
		}

		System.out.print(res);
	}
}
